package com.datastructures2.tree2;

/**
 * 二项队列
 * @author MaoLin Wang
 * @date 2020/2/1618:20
 */
public class BinomialQueue<T extends Comparable<? super T>> {

    public BinomialQueue() {
        theTrees=new Node[DEFAULT_TREES];
        makeEmpty();
    }

    public BinomialQueue(T item) {
        this.currentSize = 1;
        theTrees=new Node[1];
        theTrees[0]=new Node<>(item,null,null);
    }

    /**
     * 合并两个同样大小的二项树
     * @param t1
     * @param t2
     * @return
     */
    public Node<T> combineTrees(Node<T> t1,Node<T> t2){
        if (t1.element.compareTo(t2.element)>0){
            return combineTrees(t2,t1);
        }
        t2.nextSibling =t1.leftChild;
        t1.leftChild=t2;
        return t1;
    }
    public void merge(BinomialQueue<T> rhs){
        if (this==rhs)return;
        
        currentSize+=rhs.currentSize;
        if (currentSize>capacity()){
            int maxLength=Math.max(theTrees.length,rhs.theTrees.length);
            expandTheTrees(maxLength+1);
        }

        Node<T> carry=null;
        for (int i = 0,j=1; j <= currentSize ; i++,j*=2) {
            Node<T> t1=theTrees[i];
            Node<T> t2= i<rhs.theTrees.length?rhs.theTrees[i]:null;

            int whichCase = t1 == null ? 0 : 1;
            whichCase += t2 == null ? 0 : 2;
            whichCase += carry == null ? 0 : 4;

            switch (whichCase){
                case 0:
                case 1: //this
                    break;
                case 2: //rhs
                    theTrees[i]=t2;
                    rhs.theTrees[i]=null;
                case 4: //carry
                    theTrees[i] =carry;
                    carry=null;
                    break;
                case 3: //this和rhs
                    carry=combineTrees(t1,t2);
                    theTrees[i]=rhs.theTrees[i]=null;
                    break;
                case 5://this 和 carry
                    carry=combineTrees(t1,carry);
                    theTrees[i]=null;
                    break;
                case 6: //rhs 和carry
                    carry=combineTrees(t2,carry);
                    rhs.theTrees[i]=null;
                    break;
                case 7://所有树
                    theTrees[i]=carry;
                    carry=combineTrees(t1,t2);
                    rhs.theTrees[i]=null;
                    break;
            }
        }
        for (int k = 0; k < rhs.theTrees.length; k++) {
            rhs.theTrees[k]=null;
        }
        rhs.currentSize=0;
    }
    public T deleteMin(){
        if (isEmpty()){
            System.out.println("空");
        }
        int minIndex=findMinIndex();
        T minItem = theTrees[minIndex].element;

        Node<T> deletedTree=theTrees[minIndex].leftChild;

        BinomialQueue<T>deletedQueue=new BinomialQueue<>();
        deletedQueue.expandTheTrees(minIndex+1);

        deletedQueue.currentSize=(1<<minIndex)-1;
        for (int j = minIndex-1; j >=0 ; j--) {
            deletedQueue.theTrees[j]=deletedTree;
            deletedTree=deletedTree.nextSibling;
            deletedQueue.theTrees[j].nextSibling=null;
        }

        theTrees[minIndex]=null;
        currentSize-=deletedQueue.currentSize+1;
        merge(deletedQueue);
        return minItem;

    }

    private int findMinIndex() {
        int i;
        int minIndex;
        for( i = 0; theTrees[ i ] == null; i++ )
            ;

        for( minIndex = i; i < theTrees.length; i++ )
            if( theTrees[ i ] != null &&
                    theTrees[ i ].element.compareTo( theTrees[ minIndex ].element ) < 0 )
                minIndex = i;

        return minIndex;
    }

    private boolean isEmpty() {
        return currentSize==0;
    }

    private void expandTheTrees(int newNumTrees) {
        Node<T>[] old = this.theTrees;
        int oldNumTrees=theTrees.length;
        
        theTrees=new Node[newNumTrees];

        for (int i = 0; i < Math.min(oldNumTrees,newNumTrees); i++) {
            theTrees[i]=old[i];
        }
        for (int i = oldNumTrees; i < newNumTrees; i++) {
            theTrees[i]=null;

        }
    }

    private int capacity() {
        return (1<<theTrees.length)-1;
    }

    private void makeEmpty() {
        currentSize=0;
        for (int i = 0; i < theTrees.length; i++) {
            theTrees[i]=null;
        }
    }
    public void insert( T x )
    {
        merge( new BinomialQueue<>( x ) );
    }
    private static class Node<T>{
        public Node(T element) {
            this(element,null,null);
        }

        public Node(T element, Node<T> leftChild, Node<T> nextSibling) {
            this.element = element;
            this.leftChild = leftChild;
            this.nextSibling = nextSibling;
        }

        T element;
        Node<T> leftChild;
        Node<T> nextSibling;

        @Override
        public String toString() {
            return "Node{" +
                    "element=" + element +
                    ", leftChild=" + leftChild +
                    ", nextSibling=" + nextSibling +
                    '}';
        }
    }
    private static final int DEFAULT_TREES=1;

    private int currentSize;
    /**
     * 树根节点集合
     */
    private Node<T>[] theTrees;
    public static void main( String [ ] args )
    {
        int numItems = 10000;
        BinomialQueue<Integer> h  = new BinomialQueue<>( );
        BinomialQueue<Integer> h1 = new BinomialQueue<>( );
        BinomialQueue<Integer> h2 = new BinomialQueue<>( );

        h.insert(13);
        h1.insert(23);
        h1.insert(24);
        h1.insert(51);
        h1.insert(65);

        h2.insert(12);
        h2.insert(14);
        h2.insert(21);
        h2.insert(24);
        h2.insert(65);
        h2.insert(16);
        h2.insert(26);
        h2.insert(18);

        h.merge(h1);
        h.merge(h2);
        h.deleteMin();

        System.out.println( "Check done." );
    }
}
